/*
 * Delaunay三角剖分算法库
 */
define(["require", "exports", "./Topology"], function(require, exports, Topology) {
	function Delaunay() {
		this.Point = Point;
		this.Line = Line;
		this.Polygon = Polygon;
	}
	var topology = new Topology();
	/*
	 * 点线面几何模型
	 */
	var Point = function(coordinate, id) {
		this._id = id ? (id + "") : Math.random().toString(36).substr(2);
		this._coordinate = coordinate || [];
		this._lines = [];

		//获取点id
		this.getId = function() {
			return this._id
		};

		//设置点id
		this.setId = function(id) {
			this._id = id + "";
		};

		//获取点坐标,数据结构[x,y]
		this.getCoordinate = function() {
			return this._coordinate;
		};

		//重置点坐标 数据结构
		this.setCoordinate = function(x, y) {
			if(this._lines.length != 0) {
				return false;
			} else {
				this._coordinate = [x, y];
				return true;
			}
		};

		//设置所属线
		this.setLines = function(lines) {
			this._lines = lines;
		};

		//添加所属线
		this.addLine = function(addline) {
			for(var i in this._lines) {
				if(addline.getId() == this._lines[i].getId()) {
					return false;
				}
			}
			this._lines.push(addline);
			return true;
		};

		//删除所属线
		this.deleteLine = function(deleteline) {
			if(deleteline instanceof Line) {
				this._lines = this._lines.filter(function(item) {
					return item.getId() == deleteline.getId()
				});
			} else if(deleteline instanceof String) {
				this._lines = this._lines.filter(function(item) {
					return item.getId() == deleteline
				});
			}
		};

		//获取包含该点的所有线
		this.getLines = function() {
			return this._lines;
		};

		//获取包含该点的所有线id
		this.getLinesId = function() {
			var ids = [];
			for(var i in this._lines) {
				var line = this._lines[i];
				ids.push(line.getId());
			}
			return ids;
		};

		//获取包含该点的所有多边形
		this.getPolygons = function() {
			var polygons = [];
			for(var i in _line) {
				var line = _line[i];
				var line_polygons = line.getPolygons();
				for(var j in line_polygons) {
					var line_polygon = line_polygons[j];
					var isExist = false;
					for(var j in polygons) {
						var polygon = polygons[j];
						if(polygon.getId() == line_polygon.getId()) {
							isExist = true;
							break;
						}
					}
					if(isExist == false)
						polygons.push(line_polygon);
				}
			}
			return polygons;
		};

		//获取包含该点的所有多边形的id
		this.getPolygonsId = function() {
			var polygons = this.getPolygons();
			var ids = [];
			for(var i in polygons) {
				ids.push(polygons[i].getId());
			}
			return ids;
		};

		//销毁该点几何
		this.destroy = function() {
			if(this._lines.length != 0)
				return false;
			//清除内部属性
			this._id = null;
			this._coordinate = null;
			this._lines = null;
			return true;
		}
	};

	var Line = function() {
		this._id = Math.random().toString(36).substr(2);
		this._vertices = [];
		this._polygons = [];

		//获取线id
		this.getId = function() {
			return this._id;
		};

		/*
		 * 重置线的节点，如果线属于某个多边形的一部分则不能重置。
		 * point1,point2：重置线的两个节点。类型为Point。
		 */
		this.setVertices = function(point1, point2) {
			//如果该线属于某个多边形的一部分，则不能重置节点
			if(this._polygons.length != 0)
				return;
			//清除之前包含节点的_lines的信息
			for(var i in this._vertices) {
				this._vertices[i].deleteLine(this._id);
			}
			//对添加点设置_lines信息
			point1.addLine(this);
			point2.addLine(this);

			this._vertices = [point1, point2];
		};

		//获取节点id
		this.getVerticesId = function() {
			if(this._vertices.length == 2)
				return [this._vertices[0].getId(), this._vertices[1].getId()];
			else
				return [];
		};

		//获取节点
		this.getVertices = function() {
			return this._vertices;
		};

		//重置所属多边形
		this.setPolygons = function(polygons) {
			this._polygons = polygons;
		};

		//添加所属多边形
		this.addPolygon = function(addpolygon) {
			for(var i in this._polygons) {
				var polygon = this._polygons[i];
				if(polygon.getId() == addpolygon.getId())
					return;
			}
			this._polygons.push(addpolygon);
		};

		/*
		 * 删除所属多边形
		 * 参数 deletepolygon: 可以为Polgon对象，也可以为字符串表示Polgon对象的id
		 */
		this.deletePolygon = function(deletpolygon) {
			if(deletpolygon instanceof Point) {
				this._polygons = this._polygons.filter(function(item) {
					return item.getId() != deletpolygon.getId()
				});
			} else if(deletpolygon instanceof String) {
				this._polygons = this._polygons.filter(function(item) {
					return item.getId() != deletpolygon
				});
			}
		};

		//获取所属多边形
		this.getPolygons = function() {
			return this._polygons;
		};

		//获取所属多边形id
		this.getPolygonsId = function() {
			var ids = [];
			for(var i in this._polygons) {
				ids.push(this._polygons[i].getId());
			}
			return ids;
		};

		/*
		 * 销毁该线几何
		 * isClearVertices:是否要销毁线所包含的节点
		 */
		this.destroy = function(isClearVertices) {
			if(_polygon.length != 0)
				return false;
			//清除线包含点的_line信息
			this._vertices[0].deleteLine(this._id);
			this._vertices[1].deleteLine(this._id);
			//清除线所包含的所有节点
			if(isClearVertices == true) {
				this._vertices[0].destroy();
				this._vertices[1].destroy();
			}
			//清除内部属性
			this._id = null;
			this._vertices = null;
			this._polygons = null;
			return true;
		};
	}

	var Polygon = function() {
		this._id = Math.random().toString(36).substr(2);
		this._lines = [];

		//获取多边形id
		this.getId = function() {
			return this._id;
		};

		//获取多边形上所有节点
		this.getVertices = function() {
			var vertices = [];
			for(var i in this._lines) {
				var line = this._lines[i];
				var line_vertices = line.getVertices();
				for(var j in line_vertices) {
					var line_vertice = line_vertices[j];
					var isExist = false;
					for(var k in vertices) {
						if(vertices[k].getId() == line_vertice.getId()) {
							isExist = true;
							break;
						}
					}
					if(isExist == false)
						vertices.push(line_vertice);
				}
			}
			return vertices;
		};

		//获取多边形上所有节点id
		this.getVerticesId = function() {
			var ids = [];
			var vertices = this.getVertices();
			for(var i in vertices) {
				var point = vertices[i];
				ids.push(point.getId());
			}
			return ids;
		};

		/*
		 * 以边线来构造多边形
		 * lines：用于构造多边形的边线。结构：[line1:Line,line2:Line]
		 */
		this.constructByLines = function(lines) {
			//判断这些线是否能构成闭合的多边形
			var points_list = [];
			for(var i in lines) {
				var points = lines[i].getVertices();
				points_list.push(points[0]);
				points_list.push(points[1]);
			}
			//监测这些线相同点的数量，如果线闭合则每一个点都不唯一，有且只有一个与它相同
			var pointsIds = [];
			for(var j in points_list) {
				var id = points_list[j].getId();
				if(pointsIds[id] == null)
					pointsIds[id] = 1;
				else
					pointsIds[id]++;
			}
			for(var j in pointsIds) {
				if(pointsIds[j] != 2)
					return false;
			}
			//如果该多边形不是新生成的，修改之前包含线的多边形信息
			if(this._lines.length != 0) {
				for(var i in this._lines) {
					var line = this._lines[i];
					line.deletePolygon(this._id);
				}
			}
			this._lines = lines;
			for(var i in this._lines) {
				var line = this._lines[i];
				//给线添加所属多边形信息
				line.addPolygon(this);
			}
			return true;
		};

		/*
		 * 以一串坐标点作为节点来构造多边形，并返回结果
		 * coordinates:节点坐标。 结构：[[x1,y1],[x2,y2],、、、]
		 */
		this.constructByCoordinates = function(coordinates) {
			var points_index = topology.OutConvexPolgon(coordinates);
			var points = points_index.map(function(item) {
				var point = new Point();
				point.setCoordinate(item.coordinate[0], item.coordinate[1]);
				return point;
			});
			var lines = [];
			for(var p = 0; p < points.length; p++) {
				var next = p + 1;
				if(next == points.length)
					next = 0;
				var line = new Line();
				line.setVertices(points[p], points[next]);
				lines.push(line);
			}
			var isSuccess = this.constructByLines(lines);
			return isSuccess;
		}

		/*
		 * 以输入节点来构造多边形，并返回最终结果
		 * points:节点对象(Point)。 结构：[point1,point2,、、、]
		 */
		this.constructByPoints = function(points) {
			var coordinates = points.map(function(item) {
				return item.getCoordinate();
			});
			var points_index = topology.OutConvexPolgon(coordinates);
			var points = points_index.map(function(item) {
				return points[item.index];
			});
			for(var p = 0; p < points.length; p++) {
				var next = p + 1;
				if(next == points.length)
					next = 0;
				var line = new Line();
				line.setVertices(points[p], points[next]);
				lines.push(line);
			}
			var isSuccess = this.constructByLines(lines);
			return isSuccess;
		}

		//获取该面的所有包含线
		this.getLines = function() {
			return this._lines;
		};

		//获取该面所有包含线的id
		this.getLinesId = function() {
			var ids = [];
			for(var i in this._lines) {
				ids.push(this._lines[i].id);
			}
			return ids;
		};

		//销毁该面几何
		this.destroy = function(isClearLines, isClearVertices) {
			//如果该多边形不是新生成的，修改之前包含点和线的信息
			if(this._lines.length != 0) {
				for(var i in this._lines) {
					var line = this._lines[i];
					line.deletePolygon(this._id);
					if(isClearLines == true) {
						if(isClearVertices == true)
							line.destroy(true);
						else
							line.destroy();
					}
				}
			}
			//清除该面对象的属性
			this._id = null;
			this._lines = null;
			return true;
		};
	};

	/*
	 * 用点切割多边形
	 * 切割线要求：点必须在多边形内部，点根据多边形所有节点的连线来切割多边形
	 * polygon 表示被切割的多边形，数据结构为 Polygon
	 * point 表示插入的内部点，数据结构为 Point
	 */
	Delaunay.prototype.polygonSplitByPoint = function(polygon, point) {
		var chilPolgons = []; //被切割后的多边形
		var vertices = polygon.getVertices();
		var cutlines = []; //切割线
		var edgelines = []; //多边形边线
		//判断点与多边形的关系，如果点不在多边形内容则结束
		var rel = topology.PolygonPointRel(vertices.map(function(item) {
			return item.getCoordinate()
		}), point.getCoordinate());
		if(rel != "in")
			return;

		for(var i in vertices) {
			var line = new Line();
			line.setVertices(vertices[i], point);
			cutlines.push(line);
		}
		edgelines = polygon.getLines();
		//遍历边缘线
		for(var i in edgelines) {
			var edgeline = edgelines[i];
			var edgepoints = edgeline.getVertices();
			//查找与该边缘线相接的切割线
			var addlines = cutlines.filter(function(item) {
				var newpoints = item.getVertices();
				var newids = newpoints.map(function(item2) {
					return item2.getId()
				});
				var edgeids = edgepoints.map(function(item2) {
					return item2.getId()
				});
				var ids = newids.concat(edgeids);
				var checkids = {};
				for(var j in ids) {
					if(checkids[ids[j]] == null) {
						checkids[ids[j]] = 1;
					} else
						checkids[ids[j]]++;
				}
				for(var j in checkids) {
					if(checkids[j] > 1)
						return true;
				}
				return false;
			});
			var newpolygon = new Polygon();
			newpolygon.constructByLines([addlines[0], addlines[1], edgeline]);
			chilPolgons.push(newpolygon);
		}
		return chilPolgons;
	};

	/*
	 * 合并多边形
	 * polygons:需要合并的多边形，数据结构为 Polygon
	 */
	Delaunay.prototype.mergePolygons = function(mergepolygons) {
		var alllines = [];
		var edgelines = [];
		var mergepolygons = mergepolygons;
		for(var i in mergepolygons) {
			var lines = mergepolygons[i].getLines();
			for(var j in lines) {
				alllines.push(lines[j]);
			}
		}
		//判断每条线上相接的多边形，如果相接多边形属于合并多边形的数量为一，则表示为边线并存入edgelines中
		for(var i in alllines) {
			var line = alllines[i];
			var polygons = line.getPolygons();
			var isEdgeLine = true;
			//记录该线段周围相邻的多边形数
			var containNum = 0;
			for(var j in polygons) {
				var polygon = polygons[j];
				var num = (mergepolygons.filter(function(item) {
					return(item.getId() == polygon.getId())
				})).length;
				if(num > 0)
					containNum++;
				if(containNum == 2) {
					isEdgeLine = false;
					break;
				}
			}
			if(isEdgeLine == true)
				edgelines.push(line);
		}
		//将分析出的边线合并成多边形
		var outPolygon = new Polygon();
		outPolygon.constructByLines(edgelines);
		return outPolygon;
	}

	/*
	 * Delaunay三角剖分（Bowyer-Watson算法）
	 * points: 表示输入点集，数据结构 [[x1,y1],[x2,y2],、、、]
	 */
	Delaunay.prototype.DelaunayTriangulation = function(points) {
		var DelaunayTri_List = [];
		var Point_List = [];
		for(var i in points) {
			Point_List.push({
				"id": i,
				"coordinate": points[i]
			});
		}
		//外包边缘的点集
		var outPoint_List = topology.OutConvexPolgon(points);
		for(var i in outPoint_List) {
			var outPoint = outPoint_List[i];
			Point_List = Point_List.filter(function(item) {
				return(item.id != outPoint.index)
			});
		}
		var line_list = [];
		var outPoints = [];

		for(var i in outPoint_List)
			outPoints.push(new Point(outPoint_List[i].coordinate, outPoint_List[i].index));

		for(var i = 0; i < outPoints.length; i++) {
			var j = i + 1;
			if(j == outPoints.length)
				j = 0;
			var point1 = outPoints[i];
			var point2 = outPoints[j];
			var line = new Line();
			line.setVertices(point1, point2);
			line_list.push(line);
		}
		var firstPolygon = new Polygon();
		firstPolygon.constructByLines(line_list);
		DelaunayTri_List = [firstPolygon];

		//上面已完成初始多边形的构建，下面开始插点
		for(var i = 0; i < Point_List.length; i++) {
			var insertPoint = new Point(Point_List[i].coordinate, Point_List[i].id);
			//判断插入点落入多边形是否为三角形，如果不是三角形则直接切割
			var overlayPolygon = DelaunayTri_List.filter(function(item) {
				var polygonPoints = item.getVertices().map(function(item2) {
					return item2.getCoordinate()
				});
				var rel = topology.PolygonPointRel(polygonPoints, insertPoint.getCoordinate());
				if(rel == "in")
					return true;
				else
					return false;
			}.bind(this));
			//获取所覆盖的多边形
			overlayPolygon = overlayPolygon[0];
			//如果该多边形不为三角形
			if(overlayPolygon != null && overlayPolygon.getLines().length > 3) {
				//直接分割多边形
				var chiltri = this.polygonSplitByPoint(overlayPolygon, insertPoint);
				for(var j in chiltri) {
					DelaunayTri_List.push(chiltri[j]);
				}
				DelaunayTri_List = DelaunayTri_List.filter(function(item) {
					return item.getId() != overlayPolygon.getId()
				});
				overlayPolygon.destroy();
				continue;
			}
			//查找插入点周围的影响三角形
			var influnceTris = DelaunayTri_List.filter(function(item) {
				var points = item.getVertices().map(function(item2) {
					return item2.getCoordinate()
				});
				var circle = topology.TriangleGetCircumcircle(points);
				var radius = circle.radius;
				var point = circle.coordinate;
				var inPoint = insertPoint.getCoordinate();
				var dis = Math.sqrt(Math.pow(inPoint[0] - point[0], 2) + Math.pow(inPoint[1] - point[1], 2));
				if(dis < radius)
					return true;
				else
					return false;
			}.bind(this));
			//将影响三角形合并成多边形
			var mergePolygon = this.mergePolygons(influnceTris);
			//销毁影响三角形数据对象
			for(var j in influnceTris) {
				var tri = influnceTris[j];
				DelaunayTri_List = DelaunayTri_List.filter(function(item) {
					return tri.getId() != item.getId()
				});
				tri.destroy();
			}
			//将多边形分割，并将分割后的三角形存入三角形列表中
			var chiltri = this.polygonSplitByPoint(mergePolygon, insertPoint);
			for(var j in chiltri) {
				DelaunayTri_List.push(chiltri[j]);
			}
			//销毁多边形对象
			mergePolygon.destroy();
		}
		return DelaunayTri_List;
	}
	return Delaunay;
});